package a10_动态规划;

/**
 * <p>
 * a52_回文子串复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/5/19
 */
public class a52_回文子串复习3 {
    public static void main(String[] args) {
        System.out.println(countSubstrings("aaaaa"));
    }
    //dp[i][j]:i和j是不是回文子串

    //递推公式：
    //chars[i] == chars[j]
    //  j - i <= 1 dp[i][j]=true
    //  dp[i+1][j-1] == true dp[i][j]=true

    //来自于：左下
    public static int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];

        int result = 0;


        for (int i = chars.length - 1; i >= 0; i--) {
            for (int j = i; j < chars.length; j++) {
                if(chars[i] == chars[j]){
                    if(j - i <= 1){
                        dp[i][j]=true;
                        result++;
                    }else {
                        if(dp[i+1][j-1] == true){
                            dp[i][j]=true;
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
}
